/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

import org.junit.Test;

/**
 * <p>
 * 判断是否有环并返回环的位置节点，如果不存在返回空.不使用额外的空间
 * 
 * Given a linked list, return the node where the cycle begins. If there is no cycle,
 * return null.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月17日
 */
public class LinkedListCycleII {

    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null){
            return null;
        }
        if(head.next==head){
            return head;
        }
        ListNode slow = head;
        ListNode fast = slow.next.next;
        if(fast==slow){
            return head;
        }
        int size = 0;
        while(fast!=null && fast.next!=null){
            if(fast==slow){
                size = getCycleSize(slow);
                System.out.println("size:"+size);
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //类似于求链表的公共交点一样
        if(size!=0){
            fast = head;
            for(int i=0;i<size;i++){
                fast = fast.next;
            }
            System.out.println("fast:"+fast);
            slow = head;
            System.out.println("slow:"+slow);
            while(slow!=fast){
                slow = slow.next;
                fast = fast.next;
                if(slow==fast){
                    return slow;  
                }
            }
//            return slow;
        }
        return null;
    }

    /**
     * 获得环的的大小
     * @param slow
     * @return
     * @author towan
     * 2015年6月17日
     */
    private int getCycleSize(ListNode slow) {
        ListNode node = slow;
        int size = 1;
        while(node.next != slow){
            node = node.next;
            size++;
        }
        return size;
    }
    @Test
    public void testCase1(){
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        head.next = node2;
        node2.next = head;
        ListNode detectCycle = detectCycle(head);
        System.out.println("node:"+detectCycle);
    }
    @Test
    public void testCase2(){
        //[3,2,0,-4], tail connects to node index 1
        ListNode head = new ListNode(3);
        ListNode node2 = new ListNode(2);
        head.next = node2;
        ListNode node3 = new ListNode(0);
        node2.next = node3;
        ListNode node4 = new ListNode(-4);
        node3.next = node4;
        node4.next = node2;
        ListNode detectCycle = detectCycle(head);
        System.out.println("node:"+detectCycle);
    }
}
